package com.zf.sort;

import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;

public class SortTest {
    public static void main(String[] args) {
        int arr[] = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0};
        int num = 8000000;
        int[] arr2 = new int[num];
        for (int i = 0; i < num; i++) {
            arr2[i] = (int) (Math.random() * 8000000);
        }

        System.out.println("排序前");
        Date data1 = new Date();
        SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
        String date1Str = simpleDateFormat.format(data1);
        System.out.println("排序前的时间是=" + date1Str);

//        bubbleSort(arr);
//        selectSort(arr2);
//        insertSort(arr2);
//        shellSort(arr2);
//        shellSort2(arr2);
//        quickSort(arr, 0, arr.length - 1);
        radixSort(arr2);
        System.out.println("=======排序后=======");
//        System.out.println(Arrays.toString(arr));
//        System.out.println(Arrays.toString(arr));
//        System.out.println(Arrays.toString(arr2));
//        System.out.println(Arrays.toString(arr2));



        Date data2 = new Date();
        String date2Str = simpleDateFormat.format(data2);
        System.out.println("排序后的时间是=" + date2Str);


    }

    public static void radixSort(int[] arr){
        //1. 得到数组中最大的数的位数
        int max = arr[0];
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] > max){
                max = arr[i];
            }
        }

        //得到最大数是几位数
        int maxLength = (max + "").length();


        //定义一个二维数组，表示 10 个桶, 每个桶就是一个一维数组
        // 说明
        // 1. 二维数组包含 10 个一维数组
        // 2. 为了防止在放入数的时候，数据溢出，则每个一维数组(桶)，大小定为 arr.length
        // 3. 名明确，基数排序是使用空间换时间的经典算法

        int[][] bucket = new int[10][arr.length];

        //为了记录每个桶中，实际存放了多少个数据,我们定义一个一维数组来记录各个桶的每次放入的数据个数
        // 可以这里理解
        // 比如：bucketElementCounts[0] , 记录的就是 bucket[0] 桶的放入数据个数
        int[] bucketElementCounts = new int[10];

        //这里我们使用循环将代码处理

        for (int i = 0, n = 1; i < maxLength; i++, n *= 10) {
            for (int j = 0; j < arr.length; j++) {
                //取出每个元素的对应位的值
                int digitOfElement = arr[j] / n  % 10;
                //放入到对应的桶中
                bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j];
                bucketElementCounts[digitOfElement]++;
            }
            int index = 0;
            //按照这个桶的顺序(一维数组的下标依次取出数据，放入原来数组)
            for (int k = 0; k < bucketElementCounts.length; k++) {
                //如果桶中，有数据，我们才放入到原数组
                if (bucketElementCounts[k] != 0){
                    for (int l = 0; l < bucketElementCounts[k]; l++) {
                        arr[index++] = bucket[k][l];
                    }
                }

                //第 i+1 轮处理后，需要将每个 bucketElementCounts[k] = 0 ！！！！
                bucketElementCounts[k] = 0;
            }
//            System.out.println("第 "+i+" 轮，对个位的排序处理 arr =" + Arrays.toString(arr));
        }

    }

    /**
     *
     * @param arr
     * @param left 左下标
     * @param right 右下标
     * pivot 中轴值
     */
    public static void quickSort(int[] arr, int left, int right){

        int l = left;
        int r = right;


        int pivot = arr[(left + right) / 2];
        int temp = 0; //临时变量，交换时使用

        while (l < r){
            while (arr[l] < pivot){
                l++;
            }
            while (arr[r] > pivot){
                r--;
            }
            if (l >= r){
                //说明pivot的左右两边的值，已经按照左边全部是小于等于pivot的值，右边全部是大于等于pivot的值
                break;
            }
            temp = arr[l];
            arr[l] = arr[r];
            arr[r] = temp;

            //如果交换完后，发现这个 arr[l] == pivot 值相等 r--， 前移
            if (arr[l] == pivot){
                r -= 1;
            }
            //如果交换完后，发现这个 arr[r] == pivot 值相等 l++， 后移
            if (arr[r] == pivot){
                l += 1;
            }
        }

        if (l == r){
            l++;
            r--;
        }

        //向左递归
        if(left < r) {
            quickSort(arr, left, r);
        }
        //向右递归
        if(right > l) {
            quickSort(arr, l, right);
        }

    }
    
    public static void shellSort(int[] arr){
        int temp = 0;
        int x = 0;
        //交换法
        for (int gap = arr.length / 2; gap > 0 ; gap /= 2) {
            for (int i = gap; i < arr.length; i++) {
                for (int j = i - gap; j >= 0; j -= gap) {
                    if (arr[j] > arr[j+gap]){
                        temp = arr[j];
                        arr[j] = arr[j+gap];
                        arr[j+gap] = temp;
                    }
                }
            }
//            System.out.println("希尔排序" + (++x) + "轮后：" + Arrays.toString(arr));
        }

    }
    //移位法，减少增量
    public static void shellSort2(int[] arr){
        for (int gap = arr.length / 2; gap > 0 ; gap /= 2) {
            for (int i = gap; i < arr.length; i++) {
                int j = i;
                int temp = arr[j];
                if (arr[j] < arr[j - gap]){
                    while (j - gap > 0 && temp < arr[j - gap]){
                        arr[j] = arr[j - gap];
                        j -= gap;
                    }
                    //推出while后，就给temp找到交换的位置
                    arr[j] = temp;
                }
            }
        }
    }

    public static void bubbleSort(int[] arr){
//
        int tmp = 0;
        boolean flag = false;
        for (int i = 0; i < arr.length - 1; i++) {
            for (int j = 0; j < arr.length - 1 - i; j++) {
                if (arr[j] > arr[j+1]){
                    flag = true;
                    tmp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = tmp;
                }
            }
            if (!flag){
                break;
            }else {
                flag = false;
            }
        }
    }

    //在推导的过程，我们发现了规律，因此，可以使用for来解决
    //选择排序时间复杂度是 O(n^2)
    public static void selectSort(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            int minIndex = i;
            int min = arr[i];
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[j] < min){
                    minIndex = j;
                    min = arr[j];
                }
            }
            if (minIndex != i){
                arr[minIndex] = arr[i];
                arr[i] = min;
            }
        }
    }

    public static void insertSort(int[] arr){
        int insertVal = 0;
        int insertIndex = 0;
        for (int i = 1; i < arr.length; i++) {
            insertVal = arr[i];
            insertIndex = i - 1;
            while (insertIndex >= 0 && insertVal < arr[insertIndex]){
                arr[insertIndex+1] = arr[insertIndex];
                insertIndex--;
            }

            if (insertIndex + 1 != i){
                arr[insertIndex + 1] = insertVal;
            }
        }

    }
}
/*        //希尔排序第一轮
        //第一轮排序，将数据分为10/2=5组，交换
        for (int i = 5; i < arr.length; i++) {
            for (int j = i - 5; j >= 0; j -= 5) {
                if (arr[j] > arr[j+5]){
                    temp = arr[j];
                    arr[j] = arr[j+5];
                    arr[j+5] = temp;
                }
            }
        }
        System.out.println("希尔排序一轮后：" + Arrays.toString(arr));

        //希尔排序第二轮
        //第二轮排序，将数据分为5/2=2组
        for (int i = 2; i < arr.length; i++) {
            for (int j = i - 2; j >= 0; j -= 2) {
                if (arr[j] > arr[j + 2]){
                    temp = arr[j];
                    arr[j] = arr[j+2];
                    arr[j+2] = temp;
                }
            }
        }
        System.out.println("希尔排序二轮后：" + Arrays.toString(arr));

        //希尔排序第三轮
        //第二轮排序，将数据分为2/2=1组
        for (int i = 1; i < arr.length; i++) {
            for (int j = i - 1; j >= 0; j -= 1) {
                if (arr[j] > arr[j + 1]){
                    temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }
            }
        }
        System.out.println("希尔排序三轮后：" + Arrays.toString(arr));*/